#include<bits/stdc++.h>
using namespace std;
inline long long quick_mod(long long b,long long p,long long mod) {
	register long long tmp=b;
    register long long ans=1;
	while(p!=0){
		if(p%2!=0){
			ans=(1ll*ans%mod
                *1ll*tmp%mod)
                %mod;
        }
		tmp=(1ll*tmp%mod
            *1ll*tmp%mod)
            %mod;
		
        p/=2;
	}
	return ans%mod;
}
inline long long read(){
	long long x;
	scanf("%lld",&x);
	return x;
}
long long IN() {
	char ch;
	long long a=0;
	while((ch=getchar())==' '||ch=='\n')
		a+=ch-'0';
	while((ch=getchar())!=' '&&ch!='\n') {
		a*=10;
		a+=ch-'0';
	}
	return a;
}
long long vs(long long m,long long n,long long mod){
    long long t=1,t_=t;
		for (long long i=1,j=m;i<=n;i++,j--) t=t*j%mod,t_=t_*i%mod;
		return t*quick_mod(t_,mod-2,mod)%mod;
}
long long lucas(long long m, long long n, long long mod){
	if(n==0) return 1;
	else{
		// long long t=1,t_=t;
		// for (long long i=1,j=m%mod;i<=n%mod;i++,j--) t*=j%mod,t_*=i%mod;
		// long long chk=t*quick_mod(t_,mod-2,mod)%mod;
		lucas(m/mod,n/mod,mod)*vs(m%mod,n%mod,mod)%mod;
	}
}
long long mod=999911659;
int main(){
	long long n=read(),g=read();

	if(g%mod==0) puts("0");
	
	long long ans=0;
	for(int i=1;i<=n;i++) 
		if(n%i==0) ans+=lucas(n,i,mod);
//		else  
	printf("%lld\n",quick_mod(g,ans,mod)%mod);
}